Search Results

Documents authored by Schepers, Markus

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.30
Cover and Hitting Times of Hyperbolic Random Graphs

Authors: Marcos Kiwi, Markus Schepers, and John Sylvester

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range (2,3). In particular, we focus on the expected times for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that up to multiplicative constants: the cover time is n(log n)², the maximum hitting time is nlog n, and the average hitting time is n. The first two results hold in expectation and a.a.s. and the last in expectation (with respect to the HRG). We prove these results by determining the effective resistance either between an average vertex and the well-connected "center" of HRGs or between an appropriately chosen collection of extremal vertices. We bound the effective resistance by the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane on which we overlay a forest-like structure.
Cite as

Marcos Kiwi, Markus Schepers, and John Sylvester. Cover and Hitting Times of Hyperbolic Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kiwi_et_al:LIPIcs.APPROX/RANDOM.2022.30,
  author =	{Kiwi, Marcos and Schepers, Markus and Sylvester, John},
  title =	{{Cover and Hitting Times of Hyperbolic Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.30},
  URN =		{urn:nbn:de:0030-drops-171523},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.30},
  annote =	{Keywords: Random walk, hyperbolic random graph, cover time, hitting time, average hitting time, target time, effective resistance, Kirchhoff index}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact